package medium最大子数组合;

import org.testng.annotations.Test;

public class Solution {
    public int maxSubArray(int[] nums) {
        int sum = -999999999;
        for (int i = 0; i < nums.length; i++) {
            int pa = 0;
            for (int j = i; j < nums.length; j++) {
                pa = pa + nums[j];
                if (pa>sum)
                    sum = pa;
            }
        }
        return sum;
    }

    public int maxSubArray1(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(res, sum);
        }
        return res;
    }
    public int maxSubArray2(int[] nums) {
        int pre = 0, maxAns = nums[0];
        for (int x : nums) {
            pre = Math.max(pre + x, x);
            System.out.println(pre);
            maxAns = Math.max(maxAns, pre);
        }
        return maxAns;
    }
    @Test
    public void test(){
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(maxSubArray2(nums));
    }
}
